package com.data_structure_test.tree;

import java.util.*;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.ConcurrentSkipListSet;

public class TreeTest {

    private static Set<TreeTest> set = new ConcurrentSkipListSet<>((t1,t2)->{
        if(t1.equals(t2)){
            return 0;
        }
        return (int) (t1.a - t2.a);
    });

    private volatile long a;

    public TreeTest(){

    }

    public TreeTest(long a){
        this.a = a;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TreeTest treeTest = (TreeTest) o;
        return a == treeTest.a;
    }

    @Override
    public int hashCode() {

        return Objects.hash(a);
    }

    public static void main(String[] args){


        TreeTest t1 = new TreeTest(155555l);
        TreeTest t2 = new TreeTest(155556l);
        TreeTest t3 = new TreeTest(155557l);
        TreeTest t4 = new TreeTest(155555l);

        set.add(t1);
        set.add(t2);
        set.add(t3);
        boolean contains = set.contains(t4);
        System.out.println(contains);

        new Thread(new Runnable() {
            @Override
            public void run() {
                boolean contains = set.contains(t4);
                System.out.println(contains);
            }
        }).start();



      /*  System.out.println(t1.equals(t2));

        TreeTest test = new TreeTest();
        TreeNode root1 = new TreeNode(1);
        root1.left = null;
        root1.right = new TreeNode(2);
      //  root1.left.left = new TreeNode(1);
       // root1.left.right = new TreeNode(3);
        root1.right.left = new TreeNode(2);
        //root1.right.right = null;
       // root1.left.left.left = new TreeNode(-1);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        //root2.right = new TreeNode(3);

       // System.out.println(test.isSymmetric(root1));

       // System.out.println(test.hasPathSum(root1,-1));

        test.findMode(root1);*/
    }

    public int[] findMode(TreeNode root) {

        Map<Integer,Integer> countMap = new HashMap<>();

        foreachAndInjectCount(root,countMap);

        List<Integer> list = new ArrayList();
        int maxTimes = 0;
        for(Map.Entry<Integer,Integer> entry: countMap.entrySet()){
            int times = entry.getValue();
            int num = entry.getKey();
            if(times > maxTimes){
                list.clear();
                list.add(num);
            }
            if(times == maxTimes){
                list.add(num);
            }

        }

        int[] res = new int[list.size()];
        for(int i = 0;i < res.length - 1;i ++){
            res[i] = list.get(i);
        }
        return res;

    }

    private void foreachAndInjectCount(TreeNode root,Map<Integer,Integer> countMap){
        if(root == null){
            return;
        }
        countMap.compute(root.val,(k,v)->{

            if(v == null){
                v = 1;
            }else{
                v += 1;
            }
            return v;

        });

        foreachAndInjectCount(root.left,countMap);
        foreachAndInjectCount(root.right,countMap);
    }

    public boolean hasPathSum(TreeNode root, int sum) {

        if(root == null){
            return false;
        }

        int tmpVal = root.val;
        if(tmpVal == sum && root.left == null && root.right == null){
            return true;
        }else{
            int newSum = sum - tmpVal;
            return hasPathSum(root.left,newSum) || hasPathSum(root.right,newSum);

        }


    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public int maxDepth(TreeNode root) {
        Queue<TreeNode> queue = new ConcurrentLinkedQueue<>();
        if(root == null){
            return 0;
        }
        queue.offer(root);
        for(int i = 1;;i ++) {
            List<TreeNode> tmpList = new ArrayList<>();
            while (!queue.isEmpty()){
              TreeNode tmp = queue.poll();
              if(tmp.left != null) {
                  tmpList.add(tmp.left);
              }
              if(tmp.right != null) {
                  tmpList.add(tmp.right);
              }
            }
            for(TreeNode node : tmpList){
                queue.offer(node);
            }
            if(queue.isEmpty()){
                return i;
            }

        }
    }

    public boolean isSymmetric(TreeNode root) {

        TreeNode copyRoot = root;

        return isSymmetricWhile(root,copyRoot);


    }

    private boolean isSymmetricWhile(TreeNode root, TreeNode copyRoot) {

        TreeNode currRootNode = root,currCopyNode = copyRoot;
        Stack<TreeNode> rootStack = new Stack<>(),copyStack = new Stack<>();


        while(currRootNode != null || !rootStack.isEmpty()){

            if(currRootNode != null){
                if(currCopyNode == null){
                    return false;
                }
                while(true){
                    if(currRootNode == null){
                        break;
                    }
                    if(currCopyNode == null){
                        return false;
                    }
                    if(currRootNode.val != currCopyNode.val){
                        return false;
                    }
                    rootStack.push(currRootNode);
                    copyStack.push(currCopyNode);

                    currRootNode = currRootNode.left;
                    currCopyNode = currCopyNode.right;
                }
            }else{
                while(currRootNode == null&& !rootStack.isEmpty()) {
                    if(currRootNode == null && currCopyNode != null){
                        return false;
                    }
                    if(copyStack.isEmpty()){
                        return false;
                    }
                    currRootNode = rootStack.pop().right;
                    currCopyNode = copyStack.pop().left;
                }
            }

        }

        return true;

    }

    private boolean isSymmetricRecursive(TreeNode p, TreeNode q) {

        if((p == null && q != null) || (p != null && q == null)){
            return false;
        }

        if(p == null || q == null){
            return true;
        }

        if(p.val != q.val){
            return false;
        }else{
            return isSymmetricRecursive(p.left,q.right) && isSymmetricRecursive(p.right,q.left);
        }


    }

    public boolean isSameTree(TreeNode p, TreeNode q) {

        return foreachAndCheck(p,q);


    }

    private boolean foreachAndCheck(TreeNode p, TreeNode q){

        if((p == null && q != null) || (p != null && q == null)){
            return false;
        }

        if(p == null || q == null){
            return true;
        }

        if(p.val != q.val){
            return false;
        }else{
            return foreachAndCheck(p.left,q.left) && foreachAndCheck(p.right,q.right);
        }
    }
}
